Polynomial Logic & Algorithms
Module 02 / Lesson 07
Concept Visualization
Polynomials in Cryptography
Polynomials are not just for algebra; in cryptography, we use them to represent data blocks. A polynomial is defined as an expression like $A(x) = a_n x^n + ... + a_1 x + a_0$. In systems like AES, the coefficients are restricted to a finite field (usually $GF(2)$).
Binary Representation:
The byte 10011011 can be represented as the polynomial:
x^7 + x^4 + x^3 + x^1 + 1
Core Operations:
- Addition: In $GF(2)$, this is simply a logical XOR operation.
- Multiplication: Performed like standard algebra but coefficients are reduced mod $p$.
- Reduction: Large polynomials are reduced using an Irreducible Polynomial (similar to prime numbers).
Python Polynomial Addition (XOR)
def poly_add_gf2(poly1, poly2):
# Addition in GF(2) is bitwise XOR
# poly1 and poly2 are binary strings like '1101'
# Pad shorter string with zeros
max_len = max(len(poly1), len(poly2))
p1 = poly1.zfill(max_len)
p2 = poly2.zfill(max_len)
result = ""
for b1, b2 in zip(p1, p2):
# 1+1=0, 1+0=1, 0+0=0 (XOR logic)
res_bit = int(b1) ^ int(b2)
result += str(res_bit)
return result.lstrip('0') or '0'
# Example: (x^2 + 1) + (x^2 + x)
# Binary: 101 + 110 = 011 (x + 1)
print(f"Result: {poly_add_gf2('101', '110')}") # Output: 11